package cn.zifangsky.queue;


import java.util.function.Consumer;

/**
 * 基于简单循环数组实现的队列
 * @author zifangsky
 *
 */
public class ArrayQueue implements Queue<Integer>{
	private int front; //队首
	private int rear; //队尾
	private int capacity; //容量
	private int[] array;

	public ArrayQueue(int size) {
		capacity = size;
		front = -1;
		rear = -1;
		array = new int[size];
	}

	/**
	 * 返回队列是否为空
	 * @时间复杂度 O(1)
	 * @return
	 */
	@Override
	public boolean isEmpty(){
		return (front == -1);
	}

	/**
	 * 返回队列是否已满
	 * @时间复杂度 O(1)
	 * @return
	 */
	public boolean isFull(){
		return ((rear + 1) % capacity == front);
	}

	/**
	 * 返回存储在队列的元素个数
	 * 注：这里在计算队列大小时加了capacity，其目的是为了处理rear < front的情况
	 * @时间复杂度 O(1)
	 * @return
	 */
	@Override
	public int size(){
		if(front == -1){
			return 0;
		}

		int size = ((rear - front + 1 + capacity) % capacity);
		//刚好满队列的时候
		if(size == 0){
			return capacity;
		}else{
			return size;
		}
	}

	/**
	 * 入队
	 * @时间复杂度 O(1)
	 * @param data
	 */
	@Override
	public void push(Integer data){
		if(isFull()){
			throw new RuntimeException("Queue Overflow!");
		}else{
			rear = (rear + 1) % capacity;
			array[rear] = data;
			if(front == -1){
				front = rear;
			}
		}
	}

	/**
	 * 出队
	 * @时间复杂度 O(1)
	 * @return
	 */
	@Override
	public Integer pop(){
		if(isEmpty()){
			throw new RuntimeException("Queue Empty!");
		}else{
			int result = array[front];

			if(front == rear){ //队列已空
				front = -1;
				rear = -1;
			}else{
				front = (front + 1) % capacity;
			}
			return result;
		}
	}

	/**
	 * 返回队首的元素，但不删除
	 * @时间复杂度 O(1)
	 */
	@Override
	public Integer top() {
		if(isEmpty()){
			throw new RuntimeException("Queue Empty!");
		}else{
			return array[front];
		}
	}

	@Override
	public void clear() {
		front = -1;
		rear = -1;
		array = new int[capacity];
	}

	/**
	 * 遍历队列
	 * @时间复杂度 O(n)
	 * @return
	 */
	@Override
	public void print(Consumer<Integer> consumer) {
		if(array != null && array.length > 0){
			for(int data : array){
				consumer.accept(data);
			}
		}
	}

	/**
	 * 删除整个队列
	 * @时间复杂度 O(1)
	 * @return
	 */
	@Override
	public void deleteQueue() {
		capacity = 1;
		front = -1;
		rear = -1;
		array = new int[1];
	}

}
